package company.rapacity;

import java.util.*;

/**
 * 517. 超级洗衣机
 * 假设有 n 台超级洗衣机放在同一排上。开始的时候，每台洗衣机内可能有一定量的衣服，也可能是空的。
 * <p>
 * 在每一步操作中，你可以选择任意 m (1 <= m <= n) 台洗衣机，与此同时将每台洗衣机的一件衣服送到相邻的一台洗衣机。
 * <p>
 * 给定一个整数数组 machines 代表从左至右每台洗衣机中的衣物数量，请给出能让所有洗衣机中剩下的衣物的数量相等的 最少的操作步数 。如果不能使每台洗衣机中衣物的数量相等，则返回 -1 。
 * 示例 1：
 * <p>
 * 输入：machines = [1,0,5]
 * 输出：3
 * 解释：
 * 第一步:    1     0 <-- 5    =>    1     1     4
 * 第二步:    1 <-- 1 <-- 4    =>    2     1     3
 * 第三步:    2     1 <-- 3    =>    2     2     2
 * 示例 2：
 * <p>
 * 输入：machines = [0,3,0]
 * 输出：2
 * 解释：
 * 第一步:    0 <-- 3     0    =>    1     2     0
 * 第二步:    1     2 --> 0    =>    1     1     1
 * 示例 3：
 * <p>
 * 输入：machines = [0,2,0]
 * 输出：-1
 * 解释：
 * 不可能让所有三个洗衣机同时剩下相同数量的衣物。
 *  
 * <p>
 * 提示：
 * <p>
 * n == machines.length
 * 1 <= n <= 104
 * 0 <= machines[i] <= 105
 * <p>
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/super-washing-machines
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class FindMinMoves517 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String plate = sc.nextLine();
        String[] split = plate.replace("[", "").replace("]", "").replace(" ", "").split(",");
        int[] machines = new int[split.length];
        for (int i = 0; i < split.length; i++) {
            machines[i] = Integer.parseInt(split[i]);
        }
        System.out.println(findMinMoves1(machines));
    }

    public static int findMinMoves(int[] machines) {
        int maxValue = 0;
        int total = 0;
        int cnt = 0;
        int idx = 0;
        OptionalDouble average1 = Arrays.stream(machines).average();
        double average  = average1.getAsDouble();

        // 挑选出大于平均值的，则是需要挪动的
        Map<Integer, Integer> map = new HashMap<>();
        // 求出最大
        for (int i = 0; i < machines.length; i++) {
            if (machines[i] > maxValue) {
                maxValue = machines[i];
                idx = i;
            }
            total += machines[i];
            if (machines[i] > average) {
                map.put(i, machines[i]);
            }
        }
        int len = machines.length;

        // 不能平均衣服
        if (total % len != 0) {
            return -1;
        }

        // 计算最多的衣服需要几步能完成
        for(Integer key : map.keySet()) {
            int[] new1 = new int[key];
            System.arraycopy(machines, 0, new1, 0, key);
            int sum1 = Arrays.stream(new1).sum();
            int len2 = len - key - 1;
            int[] new2 = new int[len2];
            int sum2 = 0;
            if (key + 1 < len) {
                System.arraycopy(machines, key + 1, new2, 0, len2);
                sum2 = Arrays.stream(new2).sum();
            }

            if (sum1 < average * key) {
                machines[key - 1]++;
                machines[key]--;
                cnt += average * key - sum1;
            }
            if (key + 1 < len && machines[key] > average && sum2 < average * len2) {
                machines[key + 1]++;
                machines[key]--;
                cnt += average * len2 - sum2;
            }
        }
        return cnt;
    }

    public static int findMinMoves1(int[] machines) {
        int total = 0;
        int cnt = 0;
        OptionalDouble average1 = Arrays.stream(machines).average();
        double average  = average1.getAsDouble();

        // 挑选出大于平均值的，则是需要挪动的
        Map<Integer, Integer> map = new HashMap<>();
        // 求出最大
        for (int i = 0; i < machines.length; i++) {
            total += machines[i];
            if (machines[i] > average) {
                map.put(i, machines[i]);
            }
        }
        int len = machines.length;

        // 不能平均衣服
        if (total % len != 0) {
            return -1;
        }

        // 计算最多的衣服需要几步能完成
        for(Integer key : map.keySet()) {
            cnt+= machines[key]-average;
        }
        return cnt;
    }
}
